package com.arron.algorithm.leetcodetop100.双指针;

import com.arron.algorithm.ListNode;

/**
 * 删除链表的倒数第 N 个结点
 */
public class 删除链表的倒数第N个结点 {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        //使用虚拟节点 防止链表只有一个节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode nnode = findNnode(dummy, n + 1);

        nnode.next = nnode.next.next;

        return dummy.next;
    }

    public ListNode findNnode(ListNode head, int n){
        //使用双指针
        ListNode p1= head;
        int k =n;
        while (k>0){
            p1 = p1.next;
            k--;
        }

        ListNode p2 = head;

        while (p1!=null){
            p2= p2.next;
            p1 = p1.next;
        }
        return p2;
    }

}
